class Solution {
    public:
        int dy[4]={0,0,1,-1};
        int dx[4]={1,-1,0,0};
        vector<vector<bool>> vis;
        int m ,n;
        int ret=0;
        int numIslands(vector<vector<char>>& grid) {
            
            m = grid.size();n =grid[0].size();
            vis = vector<vector<bool>>(m,vector<bool>(n));
            for(int i =0;i<m;i++)
                for(int j =0;j<n;j++)
                {
                    if(!vis[i][j]&&grid[i][j]=='1')
                    {
                        ret++;
                        dfs(grid,i,j);
                    }
                }
            return ret;
        }
        void dfs(vector<vector<char>>& grid,int i,int j)
        {
            vis[i][j]=true;
            for(int k=0;k<4;k++)
            {
                int x = dx[k]+i;
                int y=dy[k]+j;
                if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&grid[x][y]=='1')
                {
                    dfs(grid,x,y);
                }
            }
        }
    };